原始题目：剑指 Offer 31. 栈的压入、弹出序列 (opens new window)
解题思路：
根据已有的压入序列，我们借助一个辅助栈 ，模拟压入。
压入过程中，使用索引 来指向弹出序列，如果 k 指向的弹出元素和当前 的栈顶元素相同，则将 的栈顶元素弹出， 自增，否则继续将压入序列压入 中。
如果压入序列遍历完了， 中还有数据，说明弹出序列不合法，否则 应该为空。
验证函数
**传递参数：**压入序列 ，弹出序列 。
验证过程：
- 创建一个模拟栈 ，弹出元素的索引 初始值为 。
- 遍历 ，用 表示当前压入元素
- 将 压入 中。
- 循环检查，当 不为空时，检查 的栈顶元素是否等于
- 如果相等，则 弹出栈顶元素， 自增
- 判断 是否为空
- ： 不为空， 不合法；
- ： 为空， 合法
代码：
public boolean validateStackSequences(int[] pushed, int[] popped) { if (pushed == null || popped == null || pushed.length == 0 || pushed.length != popped.length) { return true; } // helper 来模拟 pushed 的入栈 Deque<Integer> helper = new LinkedList<>(); int k = 0; for (int num : pushed) { // 模拟入栈 helper.push(num); // 如果辅助栈不为空，检查辅助栈的栈顶元素，如果和弹出序列相等就弹出 while (!helper.isEmpty() && helper.peek() == popped[k]) { helper.pop(); k++; } } return helper.isEmpty(); }@Lin2j: 代码已经复制到剪贴板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
复杂度分析
- 时间复杂度： 为 的长度，每个元素最多出入栈 次，即最多共 次出入栈操作。
- 空间复杂度： 为 的长度，辅助栈最多存储 个元素。
